public class Solution {
    //和为K的子数组
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        //dp[i]表示第i个位置和为k子数组个数
        //第一个数为k，dp[0]等于1
        if(nums[0] == k) {
            dp[0] = 1;
        }
        for(int i = 1; i < n; i++) {
            //记录i下标与前面的数组合和为k的子数组个数
            int count = 0;
            //i位置与前面位置结合
            int sum = 0;
            for(int j = i; j >= 0; j--) {
                sum += nums[j];
                if(sum == k) {
                    count++;
                }
                if(sum > k) {
                    break;
                }
            }
            dp[i] = dp[i-1] + count;
        }
        return dp[n-1];
    }

    //将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        //中间节点为根节点
        int mid = (nums.length -1)/2;
        TreeNode root = new TreeNode(nums[mid]);
        //创建左右子树
        root.left = createTree(nums,0,mid-1);
        //创建右子树
        root.right = createTree(nums,mid+1,nums.length-1);
        return root;
    }
    private TreeNode createTree(int[] nums,int start,int end) {
        if(start > end) {
            return null;
        }
        //中间节点为根节点
        int mid = (end + start)/2;
        TreeNode root = new TreeNode(nums[mid]);
        //创建左右子树
        root.left = createTree(nums,start,mid - 1);
        //创建右子树
        root.right = createTree(nums,mid + 1,end);
        return root;
    }
}
